import Foundation

// MARK: 队列

protocol Queue {
    /// 持有的元素类型
    associatedtype Element
    
    /// 是否为空
    var isEmpty: Bool { get }
    /// 栈的大小
    var size: Int { get }
    /// 栈顶元素
    var peek: Element? { get }
    
    /// 入队
    mutating func enqueue(_ newElement: Element)
    /// 出队
    mutating func dequeue() -> Element?
}

public struct IntegerQueue: Queue {
    public typealias Element = Int
    
    private var left = [Element]()
    private var right = [Element]()
    
    public var isEmpty: Bool { return left.isEmpty && right.isEmpty }
    public var size: Int { return left.count + right.count }
    public var peek: Element? { return left.isEmpty ? right.first : left.last }
    
    public mutating func enqueue(_ newElement: Element) {
        right.append(newElement)
    }
    
    public mutating func dequeue() -> Element? {
        if left.isEmpty {
            left = right.reversed()
            right.removeAll()
        }
        return left.popLast()
    }    
}
